package com.gxc.graph;

import java.util.*;

/**
 * 克鲁斯卡尔算法，适合于求边稀疏的网的最小生成树
 * 假设连通网G=（V，E），令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（V，{}），
 * 概述图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点分别在T中不同的连通分量上，则将此边加入到T中；
 * 否则，舍去此边而选择下一条代价最小的边。依此类推，直至T中所有顶点构成一个连通分量为止
 */
public class Kruskal {

    public static void main(String[] args) {
        Graph graph = BreadthFirst.createGraph();

        Set<Edge> set = kruskalUseCustom(graph);

        //set = kruskalMST(graph);
    }

    /**
     * 使用自定义的并查集
     * @param graph
     * @return
     */
    private static Set<Edge> kruskalUseCustom(Graph graph) {
        UnionLooUpSet unionLooUpSet = new UnionLooUpSet((List<Node>) graph.nodes.values());

        PriorityQueue<Edge> queue = new PriorityQueue(new EdgeComparator());
        for (Edge edge : graph.edges) {
            queue.add(edge);
        }

        Set<Edge> result = new HashSet<>();
        while (!queue.isEmpty()) {
            Edge edge = queue.poll();
            if (!unionLooUpSet.isSameSet(edge.from, edge.to)) {
                result.add(edge);
                unionLooUpSet.unionSet(edge.from, edge.to);
            }
        }
        return result;
    }

    public static class EdgeComparator implements Comparator<Edge> {

        @Override
        public int compare(Edge o1, Edge o2) {
            return o1.weight-o2.weight;
        }
    }

}
